//
// Created by Administrator on 2022/1/3.
//

#ifndef CPP_LEARNING_AVL_HPP
#define CPP_LEARNING_AVL_HPP
#include "BST.hpp"

#define Balanced(x) (stature((x).lc) == stature((x).rc))
#define BalFac(x) (stature((x).lc) - stature((x).rc))
#define AvlBalanced(x) ((-2<BalFac(x)) && (BalFac(x)<2))

enum BalanceType{
    Balanced,
    /**
     *    1
     *        2
     *            3
     */
    UnBalanced_RR,

    /**
     *          1
     *     2
     *3
     */
    UnBalanced_LL,

    /**
     *          1
     *                2
     *             3
     */

    UnBalanced_RL,

    /**
     *          1
     *    2
     *        3
     */
    UnBalanced_LR,
};

template <typename T>
class AVLTree: public BST<T>{

public:
    BinNodePosi(T) insert(const T& e);        // 重写插入或者删除
    bool remove(const T& e);                 // 重写删除  目前这个有问题

private:
    //  检查 node 的平衡情况, 插入和删除的时候使用
    BalanceType checkBalanceType(BinNodePosi(T) node);
    // 从node节点一直到root 一直检查有没有失衡
    void balanceTree(BinNodePosi(T) node);
    // 对某一个失衡的节点进行平衡
    void balanceNode(BinNodePosi(T) node );

};
// 删除的时候， 可能平衡一次还不行， 需要多次平衡
template <typename T>
void AVLTree<T>::balanceTree(BinNodePosi(T) node){
    while (node){
        // 平衡则向上继续查找
        if(AvlBalanced(*node)){
            node = node->parent;
        }else{
            BinNodePosi(T) nodeParent = node->parent;
            balanceNode(node);
            node = nodeParent;
        }
    }
}

template <typename T>
void AVLTree<T>::balanceNode(BinNodePosi(T) node){
    BalanceType balanceType = checkBalanceType(node);
    if(balanceType == Balanced) return;
    if(balanceType == UnBalanced_RR){
        BinNodePosi(T) nodeParent = node->parent;
        BinNodePosi(T)& parentReference = FromParentTo(*node);
        BinNodePosi(T) newNode = this->connect34(node, node->rc, node->rc->rc,
                        node->lc, node->rc->lc, node->rc->rc->lc,node->rc->rc->rc);

        parentReference = newNode;
        newNode->parent = nodeParent;

        this->updateHeightAbove(nodeParent);
    }

    if(balanceType == UnBalanced_RL){
        BinNodePosi(T) nodeParent = node->parent;
        BinNodePosi(T)& parentReference = FromParentTo(*node);
        BinNodePosi(T) newNode = this->connect34(node, node->rc->lc, node->rc,
                                              node->lc, node->rc->lc->lc, node->rc->lc->rc,node->rc->rc);

        parentReference = newNode;
        newNode->parent = nodeParent;

        this->updateHeightAbove(nodeParent);
    }

    if(balanceType == UnBalanced_LL){
        BinNodePosi(T) nodeParent = node->parent;
        BinNodePosi(T)& parentReference = FromParentTo(*node);

        BinNodePosi(T) newNode = this->connect34(node->lc->lc, node->lc, node,
                                              node->lc->lc->lc, node->lc->lc->rc, node->lc->rc,node->rc);

        parentReference = newNode;
        newNode->parent = nodeParent;

        this->updateHeightAbove(nodeParent);
    }

    if(balanceType == UnBalanced_LR){
        BinNodePosi(T) nodeParent = node->parent;
        BinNodePosi(T)& parentReference = FromParentTo(*node);
        BinNodePosi(T) newNode = this->connect34(node->lc, node->lc->rc, node,
                                              node->lc->lc, node->lc->rc->lc, node->lc->rc->rc,node->rc);

        parentReference = newNode;
        newNode->parent = nodeParent;

        this->updateHeightAbove(nodeParent);
    }

}

/**  1是当前node
     *          1
     *    2
     *        3
     */
template <typename T>
BalanceType AVLTree<T>::checkBalanceType(BinNodePosi(T) node){
    if(-2 < BalFac(*node) && BalFac(*node) < 2){
        return BalanceType::Balanced;
    }
    if(-2 == BalFac(*node)){
        if(-1 == BalFac(*(node->rc))){
            return BalanceType::UnBalanced_RR;
        }
        if(1 == BalFac(*(node->rc))){
            return BalanceType::UnBalanced_RL;
        }
    }


    if(2 == BalFac(*node)){
        if(-1 == BalFac(*(node->lc))){
            return BalanceType::UnBalanced_LR;
        }
        if(1 == BalFac(*(node->lc))){
            return BalanceType::UnBalanced_LL;
        }
    }

    return BalanceType::Balanced;


}


template <typename T>
BinNodePosi(T) AVLTree<T>::insert(const T& e){
    BinNodePosi(T) node = BST<T>::insert(e);

    balanceTree( node);

}
template <typename T>
bool AVLTree<T>::remove(const T& e){
    BST<T>::remove(e);
    balanceTree(this->_hot);
}


#endif //CPP_LEARNING_AVL_HPP
